1. Field of the Invention
The present invention relates generally to error check code generating devices and transmission error detecting devices, and more particularly, to an error check code generating device and a transmission error detecting device which can be formed to have a regular layout on a semiconductor substrate. The present invention has particular applicability to a data transmitting apparatus and a data receiving apparatus which adopt the frame check sequence recommended by the Community Consultative International Telephone and Telecommunications (referred to as CCITT hereinafter).
2. Description of the Background Art
In transmitting data, data error control is indispensable. Because a data error can occur in various portions of a data transmission system, a technique is required to detect the error and collect it. The cyclic redundancy check (referred to as CRC hereinafter) code method has been known as one of such techniques. When this CRC code method is applied to a data transmission system, a data error can be detected on a data receiving side. Furthermore, it is possible for the system to self-correct the data containing an error under a certain condition. The CRC code method will be described in brief below.
In the following description, data D which is represented, for example, by the following expression (1) will be described by an equation (2) EQU D=011101010 . . . (1) EQU D (X)=X.sup.7 +X.sup.6 +X.sup.5 +X.sup.3 +X.sup.3 +X.sup.1 . . . (2)
Therefore, data D (X) can be generally described as follows. ##EQU1##
First, an operation by means of module 2 (referred to as mod 2 hereinafter) for obtaining a CRC code will be described. It is assumed that, for example, data D (X) to be transmitted is represented by the expression (2) and a generating polynomial G (X) represented by the following expression (4) is applied. ##EQU2##
In order to generate a CRC code of 4 bits, the data D (X) is multiplied by X.sup.4, the product of which is divided by the generating polynomial G (X). FIG. 17A shows how this division is preformed.
As shown in FIG. 17A, the remainder obtained through this division, i.e. "1111" represents a CRC code. This CRC code CRC (X) is described by the following expression. EQU CRC (X)=X.sup.3 +X.sup.2 +X.sup.1 +X.sup.0 . . . (5)
In transmitting data, transmission data TX (X) having the code CRC (X) added to the preceding data D (X) will be applied on a transmission line. The transmission data TX (X) is, therefore, described by the following expression. ##EQU3##
The transmission data applied to the transmission line is received by a receiving apparatus. The received data RX (X) which may include a transmission error is represented by the following expression (7), i.e.: EQU RX (X)=D' (X) .multidot.X.sup.4 +CRC' (X) . . . (7)
where the data D, (X) corresponds to the data D (X) in the expression (6) and CRC' (X) corresponds to CRC (X) therein.
Transmission error detection in the receiving apparatus will be performed as follows. Initially, the data D' (X) is applied to the division in FIG. 17A instead of the data D (X), thereby to obtain a CRC code CRC'' (X). When the received CRC' (X) coincides with CRC'' (X) obtained through this operation, it is determined that there exists no transmission error. If any discrepancy is detected therebetween, which means that there has occurred a transmission error.
Generally, when data D (X) of any data length is transmitted with an additional CRC code CRC (X) of n bits, the transmission data TX (X) is represented by the following expression. EQU TX (X)=D (X) .multidot.X.sup.n +CRC (X) . . . . (8)
Besides the transmission error detection using the CRC code above, the frame check sequence (referred to as FCS hereinafter) has been known as an error detection code based on the recommendations by the CCITT. This FCS is among error detection codes for the high level data link control (referred to as HDLC hereinafter) signal and defined by the CCITT as follows.
That is, a FCS code FCS (X) is given by the following expression. EQU FCS (X)=CRCl (X)+CRC2 (X) . . . . (9)
In order to obtain CRCl (X), data D (X) having m bits to be transmitted is first multiplied by X.sup.16, the product of which is divided by the following generating polynomial G (X), leaving CRCl (X) as remainder (16 bits). EQU G (X)=X.sup.16 +X.sup.12 +X.sup.5 +X.sup.0 . . . . (10)
CRC2 (X) can be obtained as remainder (16 bits) of the division performed on X.sup.m .multidot.(X.sup.15 +X.sup.14 +. . . +X.sup.2 +X.sup.1 +X.sup.0) through the generating polynomial G (X).
The FCS code obtained through the expression (9) is, as in the case of the CRC code, added to the data D (X) to be transmitted, and applied on a transmission line therewith as transmission data TX (X).
A receiving apparatus receives the transmission data from a transmitting apparatus as received data RX (X). In order to detect any transmission error in the receiving apparatus, the received data is processed in a similar way as used in the case of the CRC code.
It is here assumed that the received data RX (X) is described by the following expression. EQU RX (X)=D' (X) .multidot.X.sup.16 +FCS'(X) . . . (11)
Initially, the data D' (X) is multiplied by X.sup.16, the product of which is divided by the generating polynomial G (X) thereby to obtain CRC1''. Then, successive 16 bits of "1" are multiplied by X.sup.m ' (m' represents figure number of the data D' (X)), the product of which is divided by the generating polynomial G (X) thereby to obtain CRC2''. By applying CRCl'' and CRC2'' to the expression (9) above, FCS'' (X) can be obtained. By comparing the received FCS' (X) with FCS'' (X) obtained through operation, transmission error can be detected. In other words, if there can be seen coincidence between the two codes, non-existence of transmission error is determined, and if not, existence of transmission error is detected.
FIG. 17B is a conceptional illustration for explaining transmission and reception of a HDLC signal. Referring to FIG. 17B, a HDLC transmitting apparatus 90 and an HDLC receiving apparatus 94 are connected through transmission lines 91 and 93. There is shown a layer 1 (92) between the transmission lines 91 and 93 which has been recommended by the CCITT. A HDLC signal applied from the transmitting apparatus 90 on the transmission line 91 is transmitted on the transmission line 93 through the layer 1 (92).
FIG. 17C is a format representation for explaining a frame format of an HDLC signal. Referring to FIG. 17C, F1 represents opening flag (1 byte). AF represents address field (2 byte). CF represents control field (1 or 2 bytes). IF represents information (data) field (260 bytes at maximum). FCS represents FCS frame (2 bytes). F2 represents closing flag (1 byte). The opening flag F1 and the closing flag F2 are predetermined to be "01111110".
When the HDLC signal is to be transmitted, the above-mentioned FCS (X) is generated by applying data D (X) comprising the address field AF, the control field CF and the information field IF to the above-described generating method for FCS. The fields AF, CF and IF, and FCS are transmitted with the opening flag Fl and the closing flag F2 at their opposite ends.
When the HDLC transmitting apparatus 90 shown in FIG. 17B transmits a HDLC signal, it inserts "0" immediately after every successive five "1"s in the fields AF, CF and IF, and FCS so as to distinguish the data in the flags F1 and F2 from the others. Meanwhile, the HDLC receiving apparatus 94 deletes the "0" s inserted immediately after the every successive five "1"s. When the HDLC transmitting apparatus 90 has no data to be transmitted, it applies successive "1"s or a successive flag pattern to the transmission line. This is referred to as "time fill".
In order to generate the CRC code or the FCS code, divisions as previously described are necessary so that a division circuit is employed. Furthermore, another division circuit is provided in the receiving apparatus so as to detect transmission error.
FIG. 18A is a circuit diagram showing an example of the conventional division circuits. Referring to FIG. 18A, this division circuit comprises shift registers 1 through 5 in successive five stages (or cascade-connected over five stages), shift registers 6 through 12 in successive seven stages, shift registers 13 through 16 in successive four stages, EXOR gates 95 and 96 interposed between the successive shift register groups, and an EXOR gate 97 connected to receive input data DI and output data DO.
FIG. 18B is a timing chart for explaining operation of the division circuit shown in FIG. 18A. FIG. 18C is an operation diagram according to which the operation is performed in the operation circuit. The operation of this division circuit will be described below.
The division circuit shown in FIG. 18A performs a division (mod 2) on input data DI by means of the generating polynomial G (X) given by the expression (10). Description will be now made on a case where input data as described below is entered. EQU DI=101001000011010001001101 . . . (12)
In operation, all the shift registers 1 through 16 are reset at the time t0. Accordingly, nodes N1 through N17 shown in FIG. 18A show data of "0". The data DI are sequentially inputted during the time interval t1 to t24. The changes of data at the respective nodes N1 through N16 and the output data DO are shown in FIG, 18B.
When a comparison is made between FIG. 18B and FIG. 8C, it can be seen that the successive 16- bits of "0" are outputted as data DO before quotient of the division is outputted as output data DO. Furthermore, the remainders at each stage in FIG. 18C coincide with the values of the shift registers at the times of t17, t19, t21, t22 and t23, respectively, as shown in FIG. 18B. The quotient of the division performed on the data DI through the generating polynomial G (X) is obtained as an output value of the shift registers at the time of t24. Therefore, it will be understood that the division circuit shown in FIG. 18A operates just according to the process shown in FIG. 18C.
FIG. 19A is a circuit diagram showing another example of the conventional division circuits. Referring to FIG. 19A, what is different from the division circuit shown in FIG. 18A is that an EXOR gate 98 is connected to the circuit instead of the EXOR gate 97.
FIG. 19B is a timing chart for explaining operation of the division circuit shown in FIG. 19A. FIG. 19C is an operation diagram according to which the division circuit performs the operation. The operation of this division circuit will be described below.
As in the case described above, the shift registers 1 through 16 are all reset at the time t0. Input data DI are entered during the time interval t1 through t24.
When a comparison is made between FIG. 19B and FIG. 19C a quotient obtained through a division on output data DO is outputted. The remainders at each stage shown in FIG. 19C do not coincide with the values of the shift registers shown in FIG. 19B except at the time of t24 where the entire input data DI has been entered. This means that a CRC code can be obtained at the time t24.
When the CRC code is obtained using the circuit shown in FIG. 18A, it is necessary to enter successive 16 bits of "0" following the input data DI. When the division circuit shown in FIG. 19A is employed, however, the CRC code can be obtained at the time (t24) when the entire input data DI has been entered so that it is possible for the circuit to generate the CRC code earlier by 16 clock cycles than the circuit of FIG. 18A. Therefore, such a division circuit as shown in FIG. 19A has been generally used to generate the CRC code.
Since in the conventional error check code generating devices and transmission error detecting devices, such division circuits as shown in FIG. 19A have been employed, the layout thereof on a semiconductor chip is irregular. In other words, the EXOR gates 95 and 96 are interposed between the shift register groups so that there cannot be seen any continuity in the layout. Additionally, only those error detection circuits have been known which are based on a specific generating polynomial G (X).